# -*- coding: utf-8 -*-
"""
    Time    : 2020/12/24 10:46 下午
    Author  : Thinkgamer
    File    : 02-二叉树.py
    Desc    : 二叉树的相关复习
        1、二叉树类的定义
        2、二叉树的深度层次遍历：先序遍历、中序遍历、后序遍历
        3、二叉树的广度优先遍历
        4、
"""


# 定义二叉树类
class TreeNode:
	def __init__(self, x):
		self.val = x
		self.left = None
		self.right = None

#          二叉树
#            A
#	        / \
#          B   C
#         / \
#        D   E
#       / \
#      F   G
#         / \
#        H   I
# 先序：A -> B -> D -> F -> G -> H -> I -> E -> C
# 中序：F -> D -> H -> G -> I -> B -> E -> A -> C
# 后序：F -> H -> I -> G -> D -> E -> B -> C -> A


class Tool:
	def __init__(self):
		pass
	
	# 创建二叉树
	def create_tree(self):
		A = TreeNode("A")
		B = TreeNode("B")
		C = TreeNode("C")
		D = TreeNode("D")
		E = TreeNode("E")
		F = TreeNode("F")
		G = TreeNode("G")
		H = TreeNode("H")
		I = TreeNode("I")
		A.left = B
		A.right = C
		B.left = D
		B.right = E
		D.left = F
		D.right = G
		G.left = H
		G.right = I
		return A
	
	# 演示 先序遍历
	# 可以通过栈实现：入栈时 先放右节点，再放左节点
	# 可以通过递归实现：先打印，然后递归左节点，再然后递归右节点
	def before_travel(self, root):
		# 通过栈实现
		result = []
		stack = [root]
		while stack:
			cur = stack.pop()
			result.append(cur.val)
			if cur.right:
				stack.append(cur.right)
			if cur.left:
				stack.append(cur.left)
		print("先序遍历的结果为：{}".format(result))
		"""
		# 通过递归实现
		if not root:
			return
		print(root.val, end=",")
		self.before_travel(root.left)
		self.before_travel(root.right)
		"""
	
	# 演示 中序遍历
	# 可以通过 栈实现：
	# 可以通过 递归实现：先递归左节点，然后打印，然后递归右节点
	def middle_travel(self, root):
		# 通过 栈 实现, 中序遍历的结果为：['F', 'D', 'H', 'G', 'I', 'B', 'E', 'A', 'C']
		result = []
		stack = []
		while stack or root:
			while root:
				stack.append(root)
				root = root.left
			root = stack.pop()
			result.append(root.val)
			root = root.right
		print("中序遍历的结果为：{}".format(result))
		"""
		# 通过递归实现
		if not root:
			return
		self.middle_travel(root.left)
		print(root.val, end=" -> ")
		self.middle_travel(root.right)
		"""
	
	# 演示 后序遍历
	# 可以通过 栈实现：入栈时，先放左节点，左节点放完时，判断当前节点是否是上一节点的左节点，是的话，把root节点定位到上一节点的右节点
	# 可以通过递归实现：先递归左节点，再递归右节点，然后打印
	def after_travel(self, root):
		# 通过栈实现
		stack = []
		result = []
		while stack or root:
			while root:
				stack.append(root)
				if root.left:
					root = root.left
				else:
					root = root.right
			s = stack.pop()
			result.append(s.val)
			
			# 如果当前节点是上一节点的左节点，则遍历右节点
			if stack and s == stack[-1].left:
				root = stack[-1].right
			else:
				root = None
		print("后序遍历的结果为：{}".format(result))
			
		"""
		# 通过递归实现
		if not root:
			return
		self.after_travel(root.left)
		self.after_travel(root.right)
		print(root.val, end=" -> ")
		"""
	
	# 演示 广度优先遍历, 即层次遍历
	def width_travel(self, root):
		if not root:
			return
		queue = [root]
		result = []
		while queue:
			size = len(queue)
			for _ in range(size):
				node = queue.pop(0)
				result.append(node.val)
				if node.left:
					queue.append(node.left)
				if node.right:
					queue.append(node.right)
		print("广度优先遍历的结果为：{}".format(result))
	
	# 求解 二叉树的最大深度, 如果root 为假，返回 0
	# 如果 root 为真，分别求左子树和右子树的最大深度，比较 left 和 right的值，返回最大的
	def max_depth(self, root):
		if not root:
			return 0
		else:
			left = self.max_depth(root.left)
			right = self.max_depth(root.right)
			return left + 1 if left > right else right + 1
		
	# 求解 二叉树的最小深度，如果root为假，返回0
	# 如果 root 为真，分别求左子树和右子树的最小深度，比较 left 和 right的值，返回最小的
	def min_depth(self, root):
		if not root:
			return 0
		else:
			left = self.min_depth(root.left)
			right = self.min_depth(root.right)
			return right + 1 if left > right else left + 1
	
	# 从根结点到叶子节点的所有路径
	# 借用深度 后序遍历的思想，当节点下无节点时，记录此时 stack 中存在的节点
	def all_travels(self, root):
		if not root:
			return
		else:
			result = list()
			stack = list()
			flag = False
			while root or stack:
				while root:
					stack.append(root)
					root = root.left
					flag = True
				if not root and flag:
					# 生成结果
					temp_result = list()
					for i in range(len(stack)):
						temp_result.append(stack[i].val)
					result.append(temp_result)
				
				flag = False
				s = stack.pop()
				if stack and s == stack[-1].left:
					root = stack[-1].right
				else:
					root = None
			print("根结点到叶子节点的所有路径为：{}".format(result))
			return result
	
	# 求两个节点的最近公共祖先
	# 存在三种情况：
	# 1、这两个节点恰好是 root 节点的左右节点，则直接返回root
	# 2、这两个节点都在 root 的左子树上，返回 find_lower_same_par_node(root.left, node1, node2)
	# 3、这两个节点都在 root 的右子树上，返回 find_lower_same_par_node(root.right, node1, node2)
	# 关于边界
	# 1、如果 root 为 none，表示没找到
	# 2、如果 root 等于 node1 或者 root 等于 node2，直接返回 root
	# 3、如果左子树没找到，返回null，证明 node1 和 node2 都在右子树，那么最终要找的最近的公共祖先就是右子树要找到的节点
	# 4、如果右子树没找到，返回null，证明 node1 和 node2 都在左子树，那么最终要找的最近的公共祖先就是左子树要找到的节点
	def find_lower_same_par_node(self, root, node1, node2):
		if not root or root == node1 or root == node2:
			return root
		else:
			left = self.find_lower_same_par_node(root.left, node1, node2)
			right = self.find_lower_same_par_node(root.right, node1, node2)
			if not left:
				return right
			elif not right:
				return left
			else:
				return root
		
	# 已知先序、中序，打印后序序列
	# 参考：https://zhuanlan.zhihu.com/p/79369751
	def print_after_travel(self, before, middle, start, end, root_index):
		if start > end:
			return
		# 找出中序 中和 start 位置相同的节点的下标
		i = middle.index(before[root_index])
		self.print_after_travel(before, middle, start, i-1, root_index + 1)
		self.print_after_travel(before, middle, i+1, end, root_index + i + 1 - start)
		# 后序 是 左右根，所以先递归，再输出
		print(before[root_index], end=" -> ")
		
	# 已知后序、中序，打印先序序列
	# 参考：https://zhuanlan.zhihu.com/p/79369751
	def print_before_travel(self, middle, after, start, end, root_index):
		if start > end:
			return
		i = middle.index(after[root_index])
		# 先序 是 根左右，所以输出，再递归
		print(after[root_index], end=" -> ")
		self.print_before_travel(middle, after, start, i - 1, root_index - end + i - 1)
		self.print_before_travel(middle, after, i + 1, end, root_index - 1)


if __name__ == "__main__":
	tool = Tool()
	# 创建一个二叉树
	root = tool.create_tree()
	# 先序遍历
	tool.before_travel(root)
	# 中序遍历
	tool.middle_travel(root)
	# 后序遍历
	tool.after_travel(root)
	
	# 广度优先遍历
	tool.width_travel(root)
	# 求二叉树的最大深度
	max_depth = tool.max_depth(root)
	print("二叉树的最大深度为：{}".format(max_depth))
	# 求二叉树的最小深度
	min_depth = tool.min_depth(root)
	print("二叉树的最小深度为：{}".format(min_depth))
	# 求 二叉树所有的路径
	tool.all_travels(root)
	# 求两个节点的最近公共祖先
	node1 = root.left.left.left
	node2 = root.left.right
	result = tool.find_lower_same_par_node(root, node1, node2)
	print("node1（{}）和 node2（{}）的最近公共祖先为：{}".format(node1.val, node2.val, result.val))
	# 已知 先序 和 中序，求后序
	# 先序：A -> B -> D -> F -> G -> H -> I -> E -> C
	# 中序：F -> D -> H -> G -> I -> B -> E -> A -> C
	# 后序：F -> H -> I -> G -> D -> E -> B -> C -> A
	before_travel = ["A", "B", "D", "F", "G", "H", "I", "E", "C"]
	middle_travel = ["F", "D", "H", "G", "I", "B", "E", "A", "C"]
	after_travel = ["F", "H", "I", "G", "D", "E", "B", "C", "A"]
	tool.print_after_travel(before_travel, middle_travel, 0, 8, 0)
	print()
	tool.print_before_travel(middle_travel, after_travel, 0, 8, 8)
